<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    class TreeNode {
      constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
      }
    }

    class BinaryTree {
      constructor() {
        this.root = null;
      }

      insert(val) {
        let node = new TreeNode(val);
        if (!this.root) {
          this.root = node;
          return;
        }
        let curr = this.root;
        while (curr) {
          if (val < curr.val) {
            if (!curr.left) {
              curr.left = node;
              break;
            } else {
              curr = curr.left;
            }
          } else {
            if (!curr.right) {
              curr.right = node;
              break;
            } else {
              curr = curr.right;
            }
          }
        }
      }

      search(val) {
        let curr = this.root;
        while (curr) {
          if (val === curr.val) {
            return true;
          } else if (val < curr.val) {
            curr = curr.left;
          } else {
            curr = curr.right;
          }
        }
        return false;
      }

      inorderTraversal(node = this.root, result = []) {
        if (!node) {
          return result;
        }
        this.inorderTraversal(node.left, result);
        result.push(node.val);
        this.inorderTraversal(node.right, result);
        return result;
      }

      preorderTraversal(node = this.root, result = []) {
        if (!node) {
          return result;
        }
        result.push(node.val);
        this.preorderTraversal(node.left, result);
        this.preorderTraversal(node.right, result);
        return result;
      }

      postorderTraversal(node = this.root, result = []) {
        if (!node) {
          return result;
        }
        this.postorderTraversal(node.left, result);
        this.postorderTraversal(node.right, result);
        result.push(node.val);
        return result;
      }
    }

    let tree = new BinaryTree();
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(3);
    tree.insert(7);
    tree.insert(12);
    tree.insert(18);
    console.log(tree.search(7)); // 输出true
    console.log(tree.inorderTraversal());     // 输出[3, 5, 7, 10, 12, 15, 18]
    console.log(tree.preorderTraversal());    // 输出[10, 5, 3, 7, 
  </script>
</body>

</html>